package interview.dynamic;

import java.util.Arrays;

/**
 * Created by yzy on 2021-03-17 23:45
 */
public class CoinChange2 {


    /**
     * 给一堆硬币组合 coins 一个数字 amount
     * 找出能组合成amount的全部组数
     *
     * dp[i] = dp[i-coins[0]] + dp[i-coins[1]] + ...
     * @param amount
     * @param coins
     * @return
     */
    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, 0);
        dp[0] = 1;
        for(int coin : coins){
            for(int i=coin; i<=amount; i++){
                dp[i] = dp[i] + dp[i-coin];
            }
        }
        return dp[amount];
    }
}
